Combinatorial Analysis

5. Set Partitions

Definition

A partition of a set S such that $S = ⋃_{j = 1}^{k} B_{j}$ . For each $j \in [1, k]$ the set $B_{j}$ is called a block of a partition $π$ and we write $| π | = k$ when $π$ consists of k blocks. In addition $S (n, k)$ denotes the number of partitions of $[n]$ having k blocks and it is called a stirling number of the second kind

Example

The set $[4]$ has seven partitions into two nonempty blocks namely

{1, 2, 3} {4} : {1, 2, 4} {3} : {1, 3, 4} {2} : {2, 3, 4} {1} :

{1, 2} {3, 4} : {1, 3} {2, 4} : {1, 4} {2, 4}

Example

Consider

$S (n, 2) = 2^{n - 1} - 1$
$S (n, n) = S (n, 1) = 1$
$S (0, 0) = 1$
$S (n, n - 1) = (\binom{n}{2})$

(1) follows since each element in $[n]$ can be assigned to either the first or second block so we have $2^{n}$ possibilities. But because we cannot have cases where all elements are in the first or in the second group in which we case we have $2^{n} - 2$ . Finally we need to account for symmetry so dividing by 2 to eliminate symmetry we have $2^{n - 1} - 1$ as desired (see below for more). The last one follows when we consider that in all such permutations at least 1 element must be of size 2. Explicitly they all look like

{x_{1} x_{2}} {x_{3}} \dots {x_{n}}

where order doesn't matter. So our problem is reduced to choosing which item will be size 2. The rest are obvious.

Definition

For $n \in N$ the total number of partitions of $[n]$ is denoted by $B (n)$ and called a Bell number. In which case it is clear that

B (n) = \sum_{k = 1}^{n} S (n, k)

since we just simply summing all cases of number of partitions which are clearly distinct independent cases

Theorem

For every $n \in N_{0}$ the following identity holds

B (n + 1) = \sum_{j = 0}^{n} (\binom{n}{j}) B (j)

Proof. By definition of bell number the LHS counts the set of of partitions of $[n + 1]$ . In which case we may do

B (n + 1) = \sum_{s = 1}^{n + 1} (\binom{n}{s - 1}) B (n + 1 - s) = \sum_{j = 0}^{n} (\binom{n}{j}) = \sum_{j = 0}^{n} (\binom{n}{j}) B (j)

where the second equality follows by considering the block containing ${n + 1}$ and enumerating through all it possible sizes. We also enumerated through all its possible members too via $(\binom{n}{s - 1})$ (number of ways to choose other $s - 1$ members not $n - 1$ in this block of size $s$ ). Then finally $B (n + 1 - s)$ counts the number of ways to partition the remaining $n + 1 - s$ elements. Clearly all distinct cases(all cases the block containing ${n + 1}$ will differ in size and members) so summing them up works. The 3rd equality follows by change of variable $j = n + 1 - s$ and the last is obvious.

9. Ordinary Generating Functions

11. Exponential Generating Functions

Definition

Let $(a_{n})_{n \geq 0}$ be a sequence of real numbers. The exponential generating function of $(a_{n})_{n \geq 0}$ is the formal series $\sum_{n = 0}^{\infty} a_{n} \frac{x^{n}}{n!}$

Example

Let us find an explicit formula for the exponential generating function $B (x)$ of the sequence $(B (n))_{n \geq 0}$ where $B (n)$ denotes the n-th Bell number. Recall that

B (n + 1) = \sum_{k = 0}^{n} (\binom{n}{k}) B (k)

Solution. First notice that

B^{'} (x) = \sum_{n = 1}^{\infty} B (n) \frac{x^{n - 1}}{(n - 1)!} = \sum_{n = 0}^{\infty} B (n + 1) \frac{x^{n}}{n!} = \sum_{n = 0}^{\infty} \sum_{k = 0}^{n} (\binom{n}{k}) B (k) \frac{x^{n}}{n!} = B (x) e^{x}

Where the 3rd equality follows by a shift in $n$ and the 3rd equality is subbin in $B (n + 1) = \sum_{k = 0}^{n} B (k)$ into our expression.Finally the last equality follows since

\sum_{n = 0}^{\infty} (\sum_{k = 0}^{n} (\binom{n}{k}) B (k) 1^{n - k}) \frac{x^{n}}{n!} = B (x) e^{x}

since

\sum_{n = 0}^{\infty} (1) \frac{x^{n}}{n!} = e^{x} and \sum_{n = 0}^{\infty} B (n) \frac{x^{n}}{n!} = B (x)

Then we obtain $e^{x} = (\ln B (x))^{'} = \frac{B^{'} (x)}{B (x)}$ then by fundamental theorem of calculus we know

\ln B (x) = e^{x} + C

but knowing $B (0) = 1$ we have $C = - 1$ so

B (x) = e^{e^{x} - 1}